package heap.数据流的中位数;


import java.util.PriorityQueue;

public class MedianFinder {


    private PriorityQueue<Integer> max;
    private PriorityQueue<Integer> min;


    public MedianFinder() {
        min = new PriorityQueue<>();
        max = new PriorityQueue<>((a, b) -> b - a);
    }

    /**
     * 保证小根堆里的元素始终比大根堆里的大 ， 且大根堆中的元素数量 >= 小根堆的元素数量 + 1
     *
     * @param num
     */
    public void addNum(int num) {
        //加入大根堆
        max.offer(num);
        //将大根堆里的最大值加入到小根堆里
        min.offer(max.poll());
        //保证小根堆中的数量
        if (min.size() > max.size()) {
            //将小根堆的最小值加入大根堆
            max.offer(min.poll());
        }
    }

    public double findMedian() {
        //根据元素数量判断取中位数
        if (max.size() == min.size()) {
            return (max.peek() + min.peek()) / 2.0d;
        } else {
            return max.peek();
        }
    }

    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(-1);
        medianFinder.addNum(-2);
        medianFinder.addNum(-3);
        medianFinder.addNum(-4);
        medianFinder.addNum(-5);
        System.out.println(medianFinder.findMedian());
    }
}
